package edu.xidian.sei.mlcs;

import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.RecursiveTask;

import edu.xidian.sei.mlcs.util.Logger;
import edu.xidian.sei.mlcs.util.Queues;
import edu.xidian.sei.mlcs.util.Stopwatch;

/**
 * 横向一路一路的进行搜索
 * 
 * @author chaostone
 */
public class Crawler {

	public static void main(String[] args) throws IOException {
		if (args.length == 0) {
			System.out.println(
					"Usage:HorizontalCrawler /path/to/your/data/file -Dmlcs.max-thread=2 -Dmlcs.auto-shrink=true -Dmlcs.optimal-only=false");
			return;
		}
		StringBuilder prompts = new StringBuilder();

		Mlcs mlcs = Mlcs.loadFromFile(args[0]);
		String maxThread = System.getProperty("mlcs.max-thread");
		if (null != maxThread) {
			mlcs.maxThread = Integer.parseInt(maxThread);
			prompts.append(" max-thread=" + maxThread);
		}

		System.out.println("Starting search " + args[0] + prompts);
		long start = System.nanoTime();
		Graph graph = new Graph(mlcs);
		Mlcs.Result result = Crawler.bfs(mlcs, graph);
		System.out.println(result.count + " mlcs(max length " + result.length + ") found, using "
				+ Stopwatch.format(System.nanoTime() - start));
		if (null != result.count) {
			int total = result.count.intValue();
			if (total > 0 && total <= 100)
				graph.printPathResult();
		}
	}

	private static Logger logger = Logger.getLogger(Crawler.class);

	public static Mlcs.Result bfs(Mlcs mlcs, Graph graph) {
		Location start = mlcs.start;
		List<Location> heads = new ArrayList<Location>();
		for (Location loc : mlcs.nextSortedLocations(start)) {
			if (graph.accessHead(start, loc))
				heads.add(loc);
		}
		search(mlcs, graph, heads);
		return graph.stat();
	}

	private static void search(Mlcs mlcs, Graph graph, List<Location> starts) {
		long startTime = System.nanoTime();
		ArrayList<Location> locations = new ArrayList<Location>();
		for (Location start : starts) {
			for (Location to : mlcs.nextLocations(start)) {
				if (graph.addEdge(start, to))
					locations.add(to);
			}
		}
		ForkJoinPool pool = null;
		if (mlcs.maxThread > 0)
			pool = new ForkJoinPool(mlcs.maxThread);
		else
			pool = new ForkJoinPool();

		int parallelism = pool.getParallelism();
		int parallelThreshhold = parallelism * 7;
		while (!locations.isEmpty()) {
			List<int[]> segs = null;
			if (locations.size() < parallelThreshhold) {
				segs = Queues.split(locations.size(), locations.size());
			} else {
				segs = Queues.split(locations.size(), parallelism);
			}

			LinkedList<ForkJoinTask<List<Location>>> tasks = new LinkedList<ForkJoinTask<List<Location>>>();
			for (int[] seg : segs) {
				tasks.addLast(pool.submit(new BFSCrawler(mlcs, locations, seg[0], seg[1])));
			}
			locations = new ArrayList<Location>();
			for (ForkJoinTask<List<Location>> task : tasks) {
				List<Location> nextLocations = task.join();
				for (Location l : nextLocations) {
					if (graph.addEdge(null, l))
						locations.add(l);
				}
			}
		}
		pool.shutdown();
		StringBuilder sb = new StringBuilder();
		for (Location start : starts) {
			sb.append(mlcs.charAt(start) + "@" + start);
			sb.append(',');
		}
		if (sb.length() > 0)
			sb.deleteCharAt(sb.length() - 1);
		logger.info("build graph(" + sb + ") using " + Stopwatch.format(System.nanoTime() - startTime));
	}

	/**
	 * 广度优先搜索(breadth-first search) 搜索locations[from,to)区间的点，将后继放入返回的集合中。
	 */
	@SuppressWarnings("serial")
	static class BFSCrawler extends RecursiveTask<List<Location>> {
		Mlcs mlcs;
		ArrayList<Location> locations;
		int from, to;

		public BFSCrawler(Mlcs mlcs, ArrayList<Location> locations, int from, int to) {
			this.mlcs = mlcs;
			this.locations = locations;
			this.from = from;
			this.to = to;
		}

		public List<Location> compute() {
			LinkedList<Location> nextLocations = new LinkedList<Location>();
			for (int i = from; i < to; i++) {
				Location current = locations.get(i);
				nextLocations.addAll(mlcs.nextLocations(current));
			}
			return nextLocations;
		}
	}
}
